package java0413;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};

public class Solution {
    // 扁平化多级双向链表
    // 递归
    public Node flatten1(Node head) {
        if (head == null) {
            return null;
        }
        if (head.child == null && head.next == null) {
            return head;
        }
        if (head.child == null) {
            Node newNext = flatten1(head.next);
            head.next = newNext;
            newNext.prev = head;
            return head;
        }
        if (head.next == null) {
            Node newNext = flatten1(head.child);
            head.next = newNext;
            newNext.prev = head;
            head.child = null;
            return head;
        }
        Node next = head.next;
        Node newNext = flatten1(head.child);
        head.next = newNext;
        newNext.prev = head;
        Node cur = head;
        for (; cur.next != null;) {
            cur = cur.next;
        }
        Node newTail = flatten1(next);
        cur.next = newTail;
        newTail.prev = cur;
        head.child = null;
        return head;
    }

    // 非递归
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        if (head.next == null && head.child == null) {
            return head;
        }
        Stack<Node> stack = new Stack<>();
        Node ret = head;
        Node cur = head;
        while (true) {
            // 有孩子
            if (cur.child != null) {
                if (cur.next != null) {
                    stack.push(cur.next);
                }
                cur.next = cur.child;
                cur.child = null;
                cur.next.prev = cur;
                cur = cur.next;
                continue;
            }
            // 有下一个
            if (cur.next != null) {
                cur = cur.next;
                continue;
            }else {
                // 栈为空
                if (stack.isEmpty() == true) {
                    break;
                }else {
                    cur.next = stack.peek();
                    stack.peek().prev = cur;
                    cur = stack.pop();
                }
            }
        }
        return ret;
    }

    // 牛客:数组中出现次数超过一半的数字
    public int MoreThanHalfNum_Solution(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int length = array.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : array) {
            int val = map.getOrDefault(x, 0);
            map.put(x, val + 1);
        }
        for (int x : array) {
            if (map.get(x) > length / 2) {
                return x;
            }
        }
        return 0;
    }

}
